package codeRandomThoughts.Test654最大二叉树;

import codeRandomThoughts.utils.TreeNode;

import java.util.Arrays;

/**
 * 要是想加速的话,就不要每次都新建数组,直接记录下标即可!!
 */
public class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        //如果nums为空,根节点为空
        if (nums.length == 0) {
            return null;
        }

        //寻找nums中的最大值,并创建根节点
        int max = nums[0];
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
                index = i;
            }
        }
        TreeNode root = new TreeNode(max);

        //分割nums为leftNums 和 rightNums
        int[] leftNums = Arrays.copyOfRange(nums,0,index);
        int[] rightNums = Arrays.copyOfRange(nums,index+1,nums.length);

        //构建左子树和右子树
        root.left = constructMaximumBinaryTree(leftNums);
        root.right = constructMaximumBinaryTree(rightNums);

        return root;
    }
}
